package com.dy.排序.内排序.基数排序;
/*
多关键字排序，如扑克有花色和面值两种关键字

最主优先，从高位到低位，
LSD从低位到高位

 */

import java.util.Arrays;

/**
 * (1)遍历序列找出最大的数(为的是确定最大的数是几位数)；
 *
 * (2)开辟一个与数组大小相同的临时数组tmp；
 *
 * (3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数；
 *
 * (4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置；
 *
 * (5)将桶中数据从小到大用tmp数组收集起来；
 *
 * (6)重复(3)(4)(5)直到所有位都被统计并计算过，用tmp收集起来；
 *
 * (7)将tmp数组拷回到原数组中；
 */
public class RadixSort {
    /*
    radix是每一位的取值范围，对于整数来说是10，对于字母来说是26
    d是位数
     */
    public static void radixSort(int nums[],int radix,int d){
        int[] tmp = new int[nums.length];

        int[] buckets = new int[radix];

        int rate=1;
        for(int i =0;i<d;i++){
            Arrays.fill(buckets,0);

            System.arraycopy(nums,0,tmp,0,nums.length);
            //统计每一个桶有多少个数
            for(int j=0;j<nums.length;j++){
                buckets[(tmp[j]/rate)%10]++;
            }
            //确定每一个桶的末尾位置，前面的位置数加当前的个数，第0个桶是第0个开始，所以从1开始循环
            for(int j=1;j<radix;j++){
                buckets[j] = buckets[j-1]+buckets[j];
            }
            for(int j = nums.length-1;j>=0;j--){
                int subKey = (tmp[j]/rate)%10;
                nums[--buckets[subKey]] = tmp[j];

            }
            rate*=10;

        }
    }

    public static void main(String[] args) {
        int nums[] = {3,1,7,2,8,99,3,1};
        //sift(nums,0,4);
        radixSort(nums,10,2);
        Arrays.stream(nums).forEach(System.out::println);
    }
}
